#include<string>
#include<variant>
#include<vector>
#include<map>
#include<stdexcept>
#include<cctype>
#include<sstream>
#include<utility>
#include<iostream>

namespace json{
struct JsonNode;

using JsonArray = std::vector<JsonNode>;

using JsonObject = std::map<std::string,JsonNode>;

struct JsonNode{
    std::variant<
        std::nullptr_t, //null
        bool,
        double,
        std::string,
        JsonArray,
        JsonObject
    >value;

    JsonNode() : value(nullptr){}
    JsonNode(std::nullptr_t) : value(nullptr){}
    JsonNode(bool b): value(b){}
    JsonNode(double d) : value(d){}
    JsonNode(const std::string s): value(s){}
    JsonNode(const char* s): value(std::string(s)){}
    JsonNode(const JsonArray& a): value(a){}
    JsonNode(const JsonObject& o): value(o){}
};

class Tokenizer{
public:
    explicit Tokenizer(const std::string& input):
     input(input),pos(0),putBackBuffer(){}

    struct Token{
        enum Type{
            LeftBrace,RightBrace,
            LeftBracket,RightBracket,
            Comma,Colon,
            String,Number,
            True,False,Null,
            Eof
        }type;
        std::string stringValue;
        double numberValue = 0.0;
        Token(Type t): type(t){}
        Token(Type t,std::string s): type(t),stringValue(std::move(s)){}
        Token(Type t,double d): type(t),numberValue(d){}
    };
    Token nextToken(){
        if(!putBackBuffer.empty()){
            Token token = putBackBuffer.back();
            putBackBuffer.pop_back();
            return token;
        }
        skipWhitespace();
        if(pos >= input.size())return {Token::Eof};
        char c = input[pos];
        switch(c){
            case '{': pos++; return {Token::LeftBrace};
            case '}': pos++; return {Token::RightBrace};
            case '[': pos++; return {Token::LeftBracket};
            case ']': pos++; return {Token::RightBracket};
            case ',': pos++; return {Token::Comma};
            case ':': pos++; return {Token::Colon};
            case '"': return parseString();
            case 't': return parseKeyword("true",4,Token::True);
            case 'f': return parseKeyword("false",5,Token::False);
            case 'n': return parseKeyword("null",4,Token::Null);

            default:
                if(isdigit(c))return parseNumber();
                if(c == '-' || c == '+')return  parseNumber();
                throw std::runtime_error(std::string("Unexpected character") + c);
        }
    }

    void putBack(const Token& token){
        putBackBuffer.push_back(token);
    }

private:
    const std::string& input;
    size_t pos;
    std::vector<Token> putBackBuffer;

    void skipWhitespace(){
        while(pos < input.size() && isspace(input[pos]))pos++;
    }

    Token parseString(){
        pos++;
        std::string str;
        while(pos < input.size()){
            char c = input[pos++];
            if(c == '"'){
                return {Token::String,str};
            }else if(c == '\\'){
                if(pos >= input.size())throw std::runtime_error("Unterminated string escape");
                c = input[pos++];
                switch(c){
                    case '"': str += '"'; break;
                    case '\\': str += '\\'; break;
                    case '/': str += '/'; break;
                    case 'b': str += '\b'; break;
                    case 'f': str += '\f'; break;
                    case 'n': str += '\n'; break;
                    case 'r': str += '\r'; break;
                    case 't': str += '\t'; break;
                    default: throw std:: runtime_error("Invalid escape character");

                }
            }else{
                str += c;
            }
        }
        throw std::runtime_error("Unterminated string");
    }

    Token parseNumber(){
        size_t start = pos;
        if (input[pos] == '-' || input[pos] == '+')pos++;
        while(pos < input.size() && isdigit(input[pos]))pos++;
        if(pos < input.size() && input[pos] == '.'){
            pos++;
            while(pos < input.size() && isdigit(input[pos]))pos++;
        }
        if(pos < input.size() && (input[pos] == 'e' || input[pos] == 'E')){
            pos++;
            if(pos < input.size() && (input[pos] == '+' || input[pos] == '-'))pos++;
            while(pos < input.size() && isdigit(input[pos]))pos++;
        }
        std::string numStr = input.substr(start,pos - start);
        try{
            double num = std::stod(numStr);
            return {Token::Number,num};
        }catch(...){
            throw std::runtime_error("Invalid number format: " + numStr);
        }
    }
    Token parseKeyword(const char* keyword,size_t len,Token::Type type){
        if(input.substr(pos,len) == keyword){
            pos += len;
            return {type};
        }
        throw std::runtime_error("Unexpected keyword");
    }
};

class Parser{
public:
    explicit Parser(const std::string& input) : tokenizer(input){}
    JsonNode parse(){
        JsonNode node = parseValue();
        Tokenizer::Token token = tokenizer.nextToken();
        if(token.type != Tokenizer::Token::Eof){
            throw std::runtime_error("Unexpected token after main value");
        }
        return node;
    }
private:
    Tokenizer tokenizer;

    JsonNode parseValue(){
        Tokenizer::Token token = tokenizer.nextToken();
        switch(token.type){
            case Tokenizer::Token::LeftBrace: return parseObject();
            case Tokenizer::Token::LeftBracket: return parseArray();
            case Tokenizer::Token::String: return JsonNode(token.stringValue);
            case Tokenizer::Token::Number: return JsonNode(token.numberValue);
            case Tokenizer::Token::True: return JsonNode(true);
            case Tokenizer::Token::False: return JsonNode(false);
            case Tokenizer::Token::Null: return  JsonNode(nullptr);
            default: throw std:: runtime_error("Unexpercted token type");

        }
    }

    JsonNode parseObject(){
        JsonObject obj;
        while(true){
            Tokenizer::Token token = tokenizer.nextToken();
            if(token.type == Tokenizer::Token::RightBrace)break;
            if(token.type != Tokenizer::Token::String){
                throw std::runtime_error("Expected string key in object");
            }
            std::string key = token.stringValue;

            token = tokenizer.nextToken();
            if(token.type != Tokenizer::Token::Colon){
                throw std::runtime_error("Expected colon after key in object");

            }
            JsonNode value = parseValue();
            obj.emplace(std::move(key),std::move(value));

            token = tokenizer.nextToken();
            if(token.type == Tokenizer::Token::RightBrace)break;
            if(token.type != Tokenizer::Token::Comma){
                throw std::runtime_error("Expected comma or } after object element");
            }
        }
        return JsonNode(obj);
    }
    JsonNode parseArray(){
        JsonArray arr;
        while(true){
            Tokenizer::Token token = tokenizer.nextToken();
            if(token.type == Tokenizer::Token::RightBracket)break;
            tokenizer.putBack(token);
            JsonNode element = parseValue();
            arr.push_back(std::move(element));
            token = tokenizer.nextToken();
            if(token.type == Tokenizer::Token::RightBracket)break;
            if(token.type != Tokenizer::Token::Comma){
                throw std::runtime_error("Expected comma or ] after array element");
            }
        }
        return JsonNode(arr);
    }
};

}


int main() {
    std::string jsonStr = R"(
        {
            "name": "John",
            "age": 30,
            "isStudent": false,
            "grades": [90, 85.5, null],
            "address": {
                "city": "New York",
                "postalCode": 10001
            }
        }
    )";

    json::Parser parser(jsonStr);
    try {
        json::JsonNode node = parser.parse();
        std::cout << "JSON parsed successfully!" << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "Error: " << e.what() << std::endl;
    }

    return 0;
}